package org.ayachinene.leetcode.problems;

import org.ayachinene.leetcode.structure.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class P112 {

    static class Solution {
        public boolean hasPathSum(TreeNode root, int targetSum) {
            if (root == null)
                return false;
            if (root.left == null && root.right == null) {
                return root.val == targetSum;
            }
            return hasPathSum(root.right, targetSum - root.val) || hasPathSum(root.left, targetSum - root.val);
        }

        /**
         * 递归查找叶子节点的个数
         *
         * @param root
         * @return
         */

        public int countLeavesNum(TreeNode root) {
            if (root == null)
                return 0;
            if (root.left == null && root.right == null) {
                return 1;
            }
            return countLeavesNum(root.left) + countLeavesNum(root.right);
        }

        /**
         * 递归得到根节点到所有叶子节点的路径
         *
         * @param root
         * @return
         */
        public void getPath(TreeNode root, String path, List<String> resPath) {
            StringBuilder tmp = new StringBuilder();
            if (root != null){
                tmp.append(root.val);
                if (root.left == null && root.right == null) {
                    resPath.add(tmp.toString());
                }else{
                    tmp.append("->");
                    getPath(root.right, tmp.toString(), resPath);
                    getPath(root.left, tmp.toString(), resPath);
                }
            }
        }

        /**
         * 递归得到根节点到所有叶子节点的路径长度
         *
         * @param root
         * @return
         */
        public void getPathSum(TreeNode root, Integer sum, List<Integer> resPathSum) {
            if (root != null){
                sum += root.val;
                if (root.left == null && root.right == null) {
                    resPathSum.add(sum);
                }else{
                    getPathSum(root.right, sum, resPathSum);
                    getPathSum(root.left, sum, resPathSum);
                }
            }
        }

    }
}
